Search for: All records

A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E=Nunsat−Nsat, spectrally filtered quantum optimization will return states with E≤qmEGS (where EGS is the ground state energy) in sub-quadratic time, where conservatively, qm≃0.59. This is in contrast to qm→0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed. 

The exponential suppression of macroscopic quantum tunneling (MQT) in the number of elements to be reconfigured is an essential element of broken symmetry phases. This suppression is also a core bottleneck in quantum algorithms, such as traversing an energy landscape in optimization, and adiabatic state preparation more generally. In this work, we demonstrate exponential acceleration of MQT through Floquet engineering with the application of a uniform, high frequency transverse drive field. Using the ferromagnetic phase of the transverse field Ising model in one and two dimensions as a prototypical example, we identify three phenomenological regimes as a function of drive strength. For weak drives, the system exhibits exponentially decaying tunneling rates but robust magnetic order; in the crossover regime at intermediate drive strength, we find polynomial decay of tunnelling alongside vanishing magnetic order; and at very strong drive strengths both the Rabi frequency and time-averaged magnetic order are approximately constant with increasing system size. We support these claims with extensive full wavefunction and tensor network numerical simulations, and theoretical analysis. An experimental test of these results presents a technologically important and novel scientific question accessible on NISQ-era quantum computers. 

For enhanced performance and privacy, companies deploying voice-activated technologies such as virtual assistants and robots are increasingly tending toward designs in which technologies only begin attending to speech once a specified wakeword is heard. Due to concerns that interactions with such technologies could lead users, especially children, to develop impolite habits, some companies have begun to develop use modes in which interactants are required to use ostensibly polite wakewords such as " Please''. In this paper, we argue that these ``please-centering'' wakewords are likely to backfire and actually discourage polite interactions due to the particular types of lexical and syntactic priming induced by those wakewords. We then present the results of a human-subject experiment (n=90) that validates those claims. 

Abstract Ecologically relevant symbioses are widespread in terrestrial arthropods but based on recent findings these specialized interactions are likely to be especially vulnerable to climate warming. Importantly, empirical data and climate models indicate that warming is occurring asynchronously, with night‐time temperatures increasing faster than daytime temperatures. Daytime (DTW) and night‐time warming (NTW) may impact ectothermic animals and their interactions differently as DTW results in greater daily temperature variation and moves organisms nearer to their thermal limits, while NTW avoids thermal limits and may relieve constraints of cooler night‐time temperatures; a nuance that has largely been ignored in the literature.In laboratory experiments, we investigated how the timing of warming influences a widespread defensive mutualism involving the pea aphidAcyrthosiphon pisum, and its heritable symbiont,Hamiltonella defensa, which protects against an important natural enemy, the parasitic waspAphidius ervi.Three aphid sublines were experimentally created from single aphid genotype susceptible toA. ervi: one line infected with a highly protectiveH. defensastrain, one infected with a moderately protective strain and one without any facultative symbiont. We examined aphid fitness in the presence and absence of parasitoids and when exposed to an average 2.5°C increase occurring across three warming scenarios (night‐time vs. daytime vs. uniform) relative to no‐warming controls.An increase of 2.5°C, as predicted to occur by the IPCC before 2100, was sufficient to disable the aphid defensive mutualism regardless of the timing of warming; a surprising result given that the daily maxima for control and NTW scenarios were identical. We also found that warming negatively impacted (a) symbiont‐mediated interactions between host and parasitoid more than symbiont‐free ones; (b) species interactions (host–parasitoid) more than each participant independently and (c) aphids more than parasitoids even though higher trophic levels are generally predicted to be more affected by warming.Here we show that 2.5°C warming, regardless of timing, negatively impacted a common microbe‐mediated defensive mutualism. While this was a laboratory‐based study, results suggest that temperature increases predicted in the near‐term may disrupt the many ecological symbioses present in terrestrial ecosystems.